package Tree;

public class 最近公共祖先 {
    //查找二叉树最近公共祖先，这个就不是搜索树了
    //有很多种解法，不过递归的最好理解
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null){
            return right;
        }
        if(right == null) {
            return left;
        }
        //不在左右里面，那就说明是当前根节点
        return root;
    }


    //找二叉搜索树的最近公共祖先， 二叉搜索树 是有数据特征的，挺好利用
    //这个祖先一定是比左边的大，比右边的小。
    public TreeNode lowestCommonAncestor_search(TreeNode root, TreeNode p, TreeNode q) {
        //比这两个都大，说明在左子树里找
        if( root.val > p.val && root.val > q.val){
            return lowestCommonAncestor_search(root.left, p, q);
        }
        if( root.val < p.val && root.val < q.val){
            return lowestCommonAncestor_search(root.right, p, q);
        }
        return root;
    }
}
